package 力扣.排序.快速排序;


public class 最大数179 {
    public static void main(String[] args) {
        int[] nums = {10,2};
//        int[] nums = {3,30,34,5,9};
//        int[] nums = {1,4,7,2,5,8,3,6,9};
//        int[] nums = {3,2,4,1};
        String s = largestNumber(nums);
        System.out.println(s);
    }

    /**
     * 原理：对于两个数而言需要比较大小，而比较的方式：比较 A+B和B+A大小，谁大谁就放在前面
     * 本质就是让我们给数组从大到小进行排列；只是比较的方法不一样
     */
    static StringBuffer ans;
    public static String largestNumber(int[] nums) {
       if (nums == null || nums.length == 0){
           return new String();
       }
       ans = new StringBuffer();//不要忘记初始化
       int N = nums.length;
       qSort2(nums,0,N);
        if (nums[0] == 0){
            return "0";
        }
        for (int t : nums) {
            ans = ans.append(String.valueOf(t));
        }
       return ans.toString();
    }

    private static void qSort(int[] nums, int b, int e) {
        if (b >= e || (b + 1)>= e){
            return;
        }
        int mid = b + ((e - b) >> 1);
        String s1 = String.valueOf(nums[mid]);//中间元素要放在循环的外面
        int l = b,i = b,r = e - 1;
        while (i <= r){
            int te = nums[i];
            //方法一：采用String的比较接口Comparable的CompareTo方法比较
            String s2 = String.valueOf(te);
            String p1 = s1 + s2;
            String p2 = s2 + s1;
            int cop = p2.compareTo(p1);
            if (cop > 0){
                swap(nums, i++, l++);
            }else if (cop == 0){
                i++;
            }else {
                swap(nums, i, r--);
            }
        }
        qSort(nums, b, l);
        qSort(nums, i, e);
    }

    private static void swap(int[] nums, int i, int i1) {
        int te = nums[i];
        nums[i] = nums[i1];
        nums[i1] = te;
    }


    private static void qSort2(int[] nums, int b, int e) {
        if (b >= e || (b + 1)>= e){
            return;
        }
        int mid = b + ((e - b) >> 1);
        int x = nums[mid];
        int l = b,i = b,r = e - 1;
        while (i <= r){
            int te = nums[i];

            long m = 10;//x
            long n = 10;//te
            while (x >= m){
                m *= 10;
            }
            while (te >= n){
                n *= 10;
            }

            long cop = (te * m + x) - (x * n + te);
            if (cop > 0){
                swap(nums, i++, l++);
            }else if (cop == 0){
                i++;
            }else {
                swap(nums, i, r--);
            }
        }
        qSort2(nums, b, l);
        qSort2(nums, i, e);
    }
}
